import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {5, 40, 3, 2, 1};
        sortNoCopy(arr, 0, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    public static int[] sort(int[] arr) {

        if (arr == null || arr.length <= 1) {
            return arr;
        }

        int middle = arr.length / 2;
        // 保证左侧有序
        int[] leftArr = sort(copyArray(arr, 0, middle));
        // 保证右侧有序
        int[] rightArr = sort(copyArray(arr, middle, arr.length));

        // 合并有序数组
        return merge(leftArr, rightArr);

    }

    public static int[] copyArray(int[] arr, int start, int end) {
        int[] newArr = new int[end - start];
        System.arraycopy(arr, start, newArr, 0, end - start);
        return newArr;
    }

    public static int[] merge(int[] arr1, int[] arr2) {

        int[] merged = new int[arr1.length + arr2.length];

        int mergedIndex = 0;
        int arr1Index = 0;
        int arr2Index = 0;
        while (arr1Index < arr1.length && arr2Index < arr2.length) {
            if (arr1[arr1Index] < arr2[arr2Index]) {
                merged[mergedIndex++] = arr1[arr1Index++];
            } else {
                merged[mergedIndex++] = arr2[arr2Index++];
            }
        }
        while (arr1Index < arr1.length) {
            merged[mergedIndex++] = arr1[arr1Index++];
        }
        while (arr2Index < arr2.length) {
            merged[mergedIndex++] = arr2[arr2Index++];
        }

        return merged;
    }

    /**
     * 直接在原数组排序
     * @param arr 需要排序的数组
     * @param start 起始下标
     * @param end 结束下标（不包含）
     */
    public static void sortNoCopy(int[] arr, int start, int end) {
        if (arr == null || end - start <= 1) {
            return;
        }

        int middle = start + (end - start) / 2;
        sortNoCopy(arr, start, middle);
        sortNoCopy(arr, middle, end);

        mergeNoCopy(arr, start, middle, end);
    }

    /**
     * arr_left: [start, middle)
     * arr_right: [middle, end)
     * @param arr 二分数组
     * @param start 起始位置
     * @param middle 中间位置
     * @param end 结束位置
     */
    public static void mergeNoCopy(int[] arr, int start, int middle, int end) {
        int[] tempArr = new int[arr.length];

        int fillIndex = start;
        int leftIndex = start;
        int rightIndex = middle;

        while (leftIndex < middle && rightIndex < end) {
            tempArr[fillIndex++] = arr[leftIndex] < arr[rightIndex] ? arr[leftIndex++] : arr[rightIndex++];
        }

        // 填充余下的位置
        while (leftIndex < middle) {
            tempArr[fillIndex++] = arr[leftIndex++];
        }
        while (rightIndex < end) {
            tempArr[fillIndex++] = arr[rightIndex++];
        }

        // 拷贝原数组
        if (end - start >= 0) {
            System.arraycopy(tempArr, start, arr, start, end - start);
        }

    }

}
